import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;

// shamir秘密共享
public class Classic_Threshold_Secret_Sharing {

    private static final Random RND = new Random();

    private static final Scanner scanner = new Scanner(System.in);

    // 将秘密分成多少个份额
    private static final int SHARING_NUM = 8;

    // 恢复秘密所需的至少份额数
    private static final int THRESHOLD = 3;

    // 安全参数
    private static final int PARAMETER = 512;

    // 安全参数
    private final int parameter;

    // 秘密子份额总数
    private final int sharingNums;

    // 秘密恢复阈值
    private final int threshold;

    private BigInteger[] secretSharings;

    private BigInteger p;

    private BigInteger secret;

    public Classic_Threshold_Secret_Sharing(int parameter, int sharingNums, int threshold) {
        this.parameter = parameter;
        this.sharingNums = sharingNums;
        this.threshold = threshold;
    }

    public static void main(String[] args) {

        Classic_Threshold_Secret_Sharing lss = new Classic_Threshold_Secret_Sharing(PARAMETER, SHARING_NUM, THRESHOLD);

        lss.p = BigInteger.probablePrime(lss.parameter, RND);
        //生成小于p的随机秘密
        lss.secret = generateRandomBigInteger(lss.p);
        System.out.println("所需要共享的秘密为：" + lss.secret);

        // 随机选择一个threshold-1次的多项式
        BigInteger[] coefficientA = new BigInteger[lss.threshold];
        coefficientA[0] = lss.secret;
        for (int i = 1; i < lss.threshold; i++) {
            coefficientA[i] = new BigInteger(lss.parameter, RND);
        }

        lss.secretSharings = new BigInteger[lss.sharingNums];
        // 计算sharingNums个子秘密
        for (int i = 0; i < lss.sharingNums; i++) {
            lss.secretSharings[i] = computeSecretSharing(coefficientA, i + 1);
            System.out.println("子秘密" + (i + 1) + "：(" + (i + 1) + "," + lss.secretSharings[i] + ")");
        }

        // 用户自行进入恢复
        System.out.print("请输入你拥有的子秘密份额数：");
        int recoverNum = scanner.nextInt();
        BigInteger[] xs = new BigInteger[recoverNum];
        BigInteger[] ys = new BigInteger[recoverNum];
        for (int i = 0; i < recoverNum; i++) {
            System.out.println("———————————————正在进行第" + (i + 1) + "轮输入———————————————");
            System.out.print("请输入x：");
            xs[i] = scanner.nextBigInteger();
            System.out.print("请输入y：");
            ys[i] = scanner.nextBigInteger();
//            ys[i] = lss.secretSharings[xs[i].subtract(BigInteger.ONE).intValue()];
        }

        BigInteger res = lss.lagrange(xs, ys);
        System.out.println("恢复出来的秘密为：" + res);
        System.out.println("恢复的结果是：" + res.equals(lss.secret));
    }

    // 计算子秘密
    private static BigInteger computeSecretSharing(BigInteger[] coefficientA, int x) {
        BigInteger res = BigInteger.ZERO;
        for (int i = 0; i < coefficientA.length; i++) {
            res = res.add(coefficientA[i].multiply(BigInteger.valueOf(x).pow(i)));
        }
        return res;
    }

    // 拉格朗日插值公式
    private BigInteger lagrange(BigInteger[] xs, BigInteger[] ys) {
        // 计算当x=0的时候即可恢复秘密
        BigInteger res = BigInteger.ZERO;
        BigInteger up;
        BigInteger down;
        for (int i = 0; i < xs.length; i++) {
            up = BigInteger.ONE;
            down = BigInteger.ONE;
            for (int j = 0; j < xs.length; j++) {
                if (i == j) continue;
                up = up.multiply(xs[j]);
                down = down.multiply(xs[j].subtract(xs[i]));
            }
            up = up.multiply(down.modInverse(p));
            up = up.multiply(ys[i]);
            res = res.add(up).mod(p);
        }
        return res;
    }

    public static BigInteger generateRandomBigInteger(BigInteger p) {
        BigInteger result;
        do {
            result = new BigInteger(p.bitLength(), RND);
        } while ((result.compareTo(p) >= 0) && (result.compareTo(BigInteger.ZERO) != 0));
        return result;
    }
}
